今天的題單：

• 01 Matrix

• K Closest Points to Origin

542. 01 Matrix

要計算每個格子距離數字是 0 的格子的最短距離。

思路: 採用 BFS 方法，建立 queue 放要檢查的格子。由於距離要從數字 0 的格子開始算，所以要先找到所有數字是 0 的格子放進 queue，從 0 的位置開始往外計算距離。對於非 0 的格子，必須要所有的鄰居都算出距離了，才能決定最短距離，不然就要再丟回 queue 裡等待。

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        vector<vector<int>> dis(mat.size(), vector<int>(mat[0].size(), INT_MAX));

        queue<pair<int, int>> q;

        for (int i = 0; i < mat.size(); i ++) {
            for (int j = 0; j < mat[0].size(); j++) {
                if (mat[i][j] == 0)
                    q.push({i, j});
            }
        }

        while (!q.empty()) {
            int i = q.front().first;
            int j = q.front().second;

            if (dis[i][j] == INT_MAX) { // not visited
                if (mat[i][j] == 0) {
                    dis[i][j] = 0;
                    // push the adjacent node
                    if (i+1 < mat.size())
                        q.push({i+1, j});
                    if (i-1 >= 0)
                        q.push({i-1, j});
                    if (j+1 < mat[0].size())
                        q.push({i, j+1});
                    if (j-1 >= 0)
                        q.push({i, j-1});
                } else {
                    int min_distance = INT_MAX;
                    if (i+1 < mat.size()) {
                        if (dis[i+1][j] == INT_MAX)
                            q.push({i+1, j});
                        min_distance = min(min_distance, dis[i+1][j]);
                    }
                    if (i-1 >= 0) {
                        if (dis[i-1][j] == INT_MAX)
                            q.push({i-1, j});
                        min_distance = min(min_distance, dis[i-1][j]);
                    }
                    if (j+1 < mat[0].size()) {
                        if (dis[i][j+1] == INT_MAX)
                            q.push({i, j+1});
                        min_distance = min(min_distance, dis[i][j+1]);
                    }
                    if (j-1 >= 0) {
                        if (dis[i][j-1] == INT_MAX)
                            q.push({i, j-1});
                        min_distance = min(min_distance, dis[i][j-1]);
                    }
                    
                    dis[i][j] = min_distance + 1;
                }
            } 
            q.pop();
        }
        return dis;
        
    }
};

973. K Closest Points to Origin

在 2D 座標平面上給 N 的點，找出距離原點最近的 K 個點。

Attempt: 暴力解，利用 priority queue 排序找出前 K 個。

class Solution {
public:

    struct cmp{
        bool operator() ( pair<int, vector<int>> a, pair<int, vector<int>> b ){      
            return a.first > b.first;
        }
    };

    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        priority_queue<pair<int, vector<int>>, vector<pair<int, vector<int>>>, cmp> pq;
        vector<vector<int>> first_k;

        for (int i = 0; i < points.size(); i++) {
            int dis = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            pq.push({dis, points[i]});
        }

        for (int i = 0; i < k; i++) {
            first_k.push_back(pq.top().second);
            pq.pop();
        }

        return first_k;
    }
};